package cn.xkai.exercise.c;

import com.google.gson.Gson;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description: 字母异位词分组
 * 自己的思路：把字符串排序后判断是否存在，存在则新增到对应key的list集合中，不存在则新建key-list
 * 借鉴的思路：同理，排序更优雅
 * @author: kaixiang
 * @date: 2022-07-28
 **/
public class Solution102 {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String temp = sort(str);
            if (map.containsKey(temp)) {
                map.get(sort(str)).add(str);
                continue;
            }
            List<String> list = new ArrayList<>();
            list.add(str);
            map.put(temp, list);
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            res.add(entry.getValue());
        }
        return res;
    }

    private String sort(String oldStr) {
        int[] strs = new int[26];
        for (int i = 0; i < oldStr.length(); i++) {
            strs[oldStr.charAt(i) - 'a'] += 1;
        }
        StringBuilder newStr = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs[i]; j++) {
                newStr.append((char) (i + 'a'));
            }
        }
        return newStr.toString();
    }

    //按字典序排序字符串
    private String sortRefer(String str) {
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        return String.valueOf(arr);
    }

    public static void main(String[] args) {
        String[] strs = {"ddddddddddg", "dgggggggggg"};
        Solution102 solution102 = new Solution102();
        System.out.println(new Gson().toJson(solution102.groupAnagrams(strs)));
    }
}
